
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */


/**
 * @param {number[]} inorder 中序数字 ：左中右
 * @param {number[]} postorder  后序数字 ：左右中
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    let index_IO = 0,
        index_PO = 0,
        length = inorder.length,
        root;

    if(length===0)return null;
    if(inorder[0]===postorder[0])
        root = new TreeNode(inorder[index_IO]);
    else
    {
        root = null;
        index_IO--;
    }
    if(length===1)return root;

    while(index_IO<length-1){
        let m = inorder[++index_IO];
        let m_index_PO = findValue(postorder, m, index_PO);
        console.log('m',m,index_PO);

        if(m_index_PO===null){
            console.log("something wrong!");
            return null;
        }

        let m_node = new TreeNode(m);

        let child_inorder = inorder.slice(index_IO+1,m_index_PO+1);
        if(index_PO===m_index_PO)m_index_PO++;
        let child_postorder = postorder.slice(index_IO,m_index_PO);

        console.log('index_PO',index_PO);
        console.log('m_index_PO',m_index_PO);
        console.log('c_io',child_inorder.join());
        console.log('c_po',child_postorder.join());
        console.log('~');

        let tmp = buildTree(child_inorder,child_postorder);

        m_node.left = root;
        m_node.right = tmp;

        root = m_node;

        index_IO = m_index_PO;

    }

    return root;

};

function findValue(arr, target, start){
    let length = arr.length;
    for(;start<length;start++){
        if(arr[start]===target){
            return start;
        }
    }
    return null;
}

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

console.log(buildTree([1,2],[1,2]));
console.log(buildTree([1,2],[2,1]));
console.log(buildTree([8,4,9,2,5,1,6,3,7],[8,9,4,5,2,6,7,3,1]));